package quickSort;


/**
 * @author talitalm
 *
 *  caracteristicas do quicksort: escolhe-se um pivot, a partir desse pivot a lista eh dividida em duas. a partir disso os numeros de cada sublista sao
 *  comparados com o pivot, o que for menor vai a esquerda pele e o que for maior vai a direita dele.
 *  
 *  	quickSort  -  partition  - swap  - gerador randomico
 *  
 *  variacoes:
 *  
 *  	Com gerador randomico: o elemento pivot eh descoberto aleatoriamente
 */

public class QuickImplementation {
	
	/**
	 * metodo de ordenacao da lista
	 * @param lista
	 * @param comecoDaLista
	 * @param fimDaLista
	 * @return o array ordenado
	 */
	public int[] quickSort(int[] lista, int comecoDaLista, int fimDaLista) {
		
		if (comecoDaLista >= fimDaLista) {
			return lista;}
		 
		int indiceDoPivo = partition(lista, comecoDaLista, fimDaLista);
		quickSort(lista, comecoDaLista, fimDaLista-1);
		quickSort(lista, comecoDaLista+1, fimDaLista);		
		
		return lista;
	}
	
	private int partition(int[] lista, int comecoDaLista, int fimDaLista) {
		int i = comecoDaLista + 1; // segundo elemento da lista
		int j = fimDaLista;
		int pivo = lista[comecoDaLista]; // primeiro elemento da lista
		
		while(i <= j) {   // enquanto o segundo elemento for melhor que o ultimo
			if (lista[i] <= pivo) { // compare o segundo da lista com o pivo
				i++; // pegue o proximo - incremento
			} else if (lista[j] > pivo){ // se o ultimo elemento for maior que o pivo
				j--; // pegue o anterior ao ultimo - decremente
			} else {
				lista = swap(lista, i, j);
			}
		}
		lista = swap(lista, comecoDaLista, i-1);
		return i-1;
		//?
	}
	

	private int[] swap(int[] lista, int menor, int maior) {
		int varTemp = lista[maior];
		lista[maior] = lista[menor];
		lista[menor] = varTemp;
		
		return null;
	}
}